/*
 *  Copyright 2005 Blandware (http://www.blandware.com)
 *
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */
package com.blandware.atleap.common.parsers.ppt;

import com.blandware.atleap.common.parsers.exception.PlainTextExtractorException;
import com.blandware.atleap.common.parsers.SpecificPlainTextExtractor;
import com.blandware.atleap.common.Constants;
import org.apache.poi.poifs.filesystem.POIFSFileSystem;
import org.apache.poi.util.LittleEndian;

import java.io.IOException;
import java.io.InputStream;
import java.io.Writer;
import java.util.HashMap;
import java.util.Map;

/**
 * An extractor that extracts a plain text from MS PowerPoint presentations.
 * Currently PowerPoint'97 and higher supported.
 *
 * @see SpecificPlainTextExtractor
 * @author Roman Puchkovskiy <a href="mailto:roman.puchkovskiy@blandware.com">
 * &lt;roman.puchkovskiy@blandware.com&gt;</a>
 * @version $Revision: 1.3 $ $Date: 2005/08/14 12:27:55 $
 */
public class PowerPointPlainTextExtractor
        implements SpecificPlainTextExtractor {
    /*
     * PowerPoint'97 presentation is stored in "PowerPoint Document" stream.
     * It is a sequence of records of the following format:
     *  + unsigned short - code; a record is a container if and
     *      only if ((code & 0xF) == 0xF)
     *  + unsigned short - type of the record
     *  + unsigned int - size of the record
     *  + size bytes - content of the record
     * If the record is a container then its content is a similar sequence of
     * records. Thus the presentation data is a tree, which leaves are called
     * 'atoms'.
     * This class uses some sort of a finite automation, where 'symbols' are
     * types of records. When a parser goes down the document tree, it
     * 'feeds' these types to the 'automation' so its state changes. When a
     * parser reaches an atom, it triggers some action.
    */

    private static final int RECORD_HEADER_LEN = 8;
    private static final int MAGIC = -476987297;

    // Pseudo record type to handle the end of a container
    private static final int SYMBOL_CONTAINER_END = -1;

    // States of an 'automation'
    private static final int STATE_NONE = -1;
    private static final int STATE_SLIDE = 3;
    private static final int STATE_SLIDE_PPDRAWING = 4;
    private static final int STATE_SLIDE_PPDRAWING_61442 = 5;
    private static final int STATE_SLIDE_PPDRAWING_61442_61443 = 6;
    private static final int STATE_SLIDE_PPDRAWING_61442_61443_61444 = 7;
    private static final int STATE_SLIDE_PPDRAWING_61442_61443_61444_61453 = 8;
    private static final int STATE_NOTES = 9;
    private static final int STATE_NOTES_PPDRAWING = 10;
    private static final int STATE_NOTES_PPDRAWING_61442 = 11;
    private static final int STATE_NOTES_PPDRAWING_61442_61443 = 12;
    private static final int STATE_NOTES_PPDRAWING_61442_61443_61444 = 13;
    private static final int STATE_NOTES_PPDRAWING_61442_61443_61444_61453 = 14;

    private static final int STATE_DOC_BEGIN = 15;
    private static final int STATE_HEADER_FOOTER = 16;
    private static final int STATE_SLIDE_LIST_WITH_TEXT = 17;

    private static final int STATE_MAIN_MASTER = 40;

    // 'Automation' actions - triggered on atoms
    private static final int ACTION_HANDLE_U16                  = 0;
    private static final int ACTION_HANDLE_ASCII                = 1;
    private static final int ACTION_HANDLE_FORMATTED            = 2;
    private static final int ACTION_HANDLE_HEADER_FOOTER        = 3;
    private static final int ACTION_HANDLE_SLIDE_PERSIST_ATOM   = 4;
    private static final int ACTION_HANDLE_PERSIST_TEXT_ASCII   = 5;
    private static final int ACTION_HANDLE_PERSIST_TEXT_U16     = 6;
    private static final int ACTION_HANDLE_SLIDE_LIST_END       = 7;

    // Record types
    private static final int RECORD_TYPE_DOCUMENT               = 1000;
    private static final int RECORD_TYPE_SLIDE                  = 1006;
    private static final int RECORD_TYPE_NOTES                  = 1008;
    private static final int RECORD_TYPE_SLIDE_PERSIST_ATOM     = 1011;
    private static final int RECORD_TYPE_MAIN_MASTER            = 1016;
    private static final int RECORD_TYPE_PPDRAWING              = 1036;
    private static final int RECORD_TYPE_TEXT_CHARS_ATOM        = 4000;
    private static final int RECORD_TYPE_TEXT_BYTES_ATOM        = 4008;
    private static final int RECORD_TYPE_CSTRING                = 4026;
    private static final int RECORD_TYPE_HEADERS_FOOTERS        = 4057;
    private static final int RECORD_TYPE_SLIDE_LIST_WITH_TEXT   = 4080;

    private Writer writer;
    // Stores a transition function for an "automation"
    private static Map map;
    // Reference to current slide
    private int curSlideRef;
    // Texts left in current slide
    private int textsLeft;
    private long[] persistentDirectories;
    private boolean inMasterSlideList;
    // If we didn't parse any slide yet in current list
    private boolean firstSlide;

    static {
        map = new HashMap();

        // In the beginning of the document
        map.put(new TransitionFunctionArg(STATE_DOC_BEGIN, RECORD_TYPE_HEADERS_FOOTERS),
                new TransitionFunctionValue(STATE_HEADER_FOOTER, 0));
        map.put(new TransitionFunctionArg(STATE_DOC_BEGIN, RECORD_TYPE_SLIDE_LIST_WITH_TEXT),
                new TransitionFunctionValue(STATE_SLIDE_LIST_WITH_TEXT, 0));

        // In slide list with text
        map.put(new TransitionFunctionArg(STATE_SLIDE_LIST_WITH_TEXT, RECORD_TYPE_SLIDE_PERSIST_ATOM),
                new TransitionFunctionValue(STATE_NONE, ACTION_HANDLE_SLIDE_PERSIST_ATOM));
        map.put(new TransitionFunctionArg(STATE_SLIDE_LIST_WITH_TEXT, RECORD_TYPE_TEXT_BYTES_ATOM),
                new TransitionFunctionValue(STATE_NONE, ACTION_HANDLE_PERSIST_TEXT_ASCII));
        map.put(new TransitionFunctionArg(STATE_SLIDE_LIST_WITH_TEXT, RECORD_TYPE_TEXT_CHARS_ATOM),
                new TransitionFunctionValue(STATE_NONE, ACTION_HANDLE_PERSIST_TEXT_U16));
        map.put(new TransitionFunctionArg(STATE_SLIDE_LIST_WITH_TEXT, SYMBOL_CONTAINER_END),
                new TransitionFunctionValue(STATE_NONE, ACTION_HANDLE_SLIDE_LIST_END));

        // In main master
        map.put(new TransitionFunctionArg(STATE_MAIN_MASTER, RECORD_TYPE_HEADERS_FOOTERS),
                new TransitionFunctionValue(STATE_HEADER_FOOTER, 0));

        // In slide
        map.put(new TransitionFunctionArg(STATE_SLIDE, RECORD_TYPE_HEADERS_FOOTERS),
                new TransitionFunctionValue(STATE_HEADER_FOOTER, 0));
        map.put(new TransitionFunctionArg(STATE_SLIDE, RECORD_TYPE_CSTRING),
                new TransitionFunctionValue(STATE_NONE, ACTION_HANDLE_U16));
        map.put(new TransitionFunctionArg(STATE_SLIDE, RECORD_TYPE_PPDRAWING),
                new TransitionFunctionValue(STATE_SLIDE_PPDRAWING, 0));
        map.put(new TransitionFunctionArg(STATE_SLIDE_PPDRAWING, 61442),
                new TransitionFunctionValue(STATE_SLIDE_PPDRAWING_61442, 0));
        map.put(new TransitionFunctionArg(STATE_SLIDE_PPDRAWING_61442, 61443),
                new TransitionFunctionValue(STATE_SLIDE_PPDRAWING_61442_61443, 0));
        map.put(new TransitionFunctionArg(STATE_SLIDE_PPDRAWING_61442_61443, 61443),
                new TransitionFunctionValue(STATE_SLIDE_PPDRAWING_61442_61443, 0));
        map.put(new TransitionFunctionArg(STATE_SLIDE_PPDRAWING_61442_61443, 61444),
                new TransitionFunctionValue(STATE_SLIDE_PPDRAWING_61442_61443_61444, 0));
        map.put(new TransitionFunctionArg(STATE_SLIDE_PPDRAWING_61442_61443_61444, 61453),
                new TransitionFunctionValue(STATE_SLIDE_PPDRAWING_61442_61443_61444_61453, 0));
        map.put(new TransitionFunctionArg(STATE_SLIDE_PPDRAWING_61442_61443_61444_61453, RECORD_TYPE_TEXT_CHARS_ATOM),
                new TransitionFunctionValue(STATE_NONE, ACTION_HANDLE_U16));
        map.put(new TransitionFunctionArg(STATE_SLIDE_PPDRAWING_61442_61443_61444_61453, RECORD_TYPE_TEXT_BYTES_ATOM),
                new TransitionFunctionValue(STATE_NONE, ACTION_HANDLE_ASCII));

        // In notes
        map.put(new TransitionFunctionArg(STATE_NOTES, RECORD_TYPE_CSTRING),
                new TransitionFunctionValue(STATE_NONE, ACTION_HANDLE_U16));
        map.put(new TransitionFunctionArg(STATE_NOTES, RECORD_TYPE_PPDRAWING),
                new TransitionFunctionValue(STATE_NOTES_PPDRAWING, 0));
        map.put(new TransitionFunctionArg(STATE_NOTES_PPDRAWING, 61442),
                new TransitionFunctionValue(STATE_NOTES_PPDRAWING_61442, 0));
        map.put(new TransitionFunctionArg(STATE_NOTES_PPDRAWING_61442, 61443),
                new TransitionFunctionValue(STATE_NOTES_PPDRAWING_61442_61443, 0));
        map.put(new TransitionFunctionArg(STATE_NOTES_PPDRAWING_61442_61443, 61443),
                new TransitionFunctionValue(STATE_NOTES_PPDRAWING_61442_61443, 0));
        map.put(new TransitionFunctionArg(STATE_NOTES_PPDRAWING_61442_61443, 61444),
                new TransitionFunctionValue(STATE_NOTES_PPDRAWING_61442_61443_61444, 0));
        map.put(new TransitionFunctionArg(STATE_NOTES_PPDRAWING_61442_61443_61444, 61453),
                new TransitionFunctionValue(STATE_NOTES_PPDRAWING_61442_61443_61444_61453, 0));
        map.put(new TransitionFunctionArg(STATE_NOTES_PPDRAWING_61442_61443_61444_61453, RECORD_TYPE_TEXT_CHARS_ATOM),
                new TransitionFunctionValue(STATE_NONE, ACTION_HANDLE_U16));
        map.put(new TransitionFunctionArg(STATE_NOTES_PPDRAWING_61442_61443_61444_61453, RECORD_TYPE_TEXT_BYTES_ATOM),
                new TransitionFunctionValue(STATE_NONE, ACTION_HANDLE_ASCII));

        // In header-footer
        map.put(new TransitionFunctionArg(STATE_HEADER_FOOTER, RECORD_TYPE_CSTRING),
                new TransitionFunctionValue(STATE_NONE, ACTION_HANDLE_HEADER_FOOTER));
    }

    public PowerPointPlainTextExtractor() {
        writer = null;
    }

    /**
     * Extracts a plain text from an MS PowerPoint presentation.
     *
     * @param input the input stream that supplies an MS PowerPoint presentation
     * for extraction
     * @param output the writer that will accept the extracted text
     * @param encoding ignored
     * @throws PlainTextExtractorException throwed on exception raised during
     * extracting
     */
    public void extract(InputStream input, Writer output, String encoding)
            throws PlainTextExtractorException {
        writer = output;

        try {
            POIFSFileSystem fs = new POIFSFileSystem(input);
            // First obtain a UserEdit record
            InputStream currentUserStream = fs.createDocumentInputStream("Current User");
            byte[] currentUserBytes = new byte[currentUserStream.available()];
            currentUserStream.read(currentUserBytes);
            currentUserStream.close();
            int magic = LittleEndian.getInt(currentUserBytes, 12);
            if (magic != MAGIC) {
                throw new PlainTextExtractorException("That's not a supported PowerPoint Document");
            } else {
                int lastEdit = (int) LittleEndian.getUInt(currentUserBytes, 16);
                InputStream documentStream = fs.createDocumentInputStream("PowerPoint Document");
                byte[] documentBytes = new byte[documentStream.available()];
                documentStream.read(documentBytes);
                documentStream.close();

                // Map persistent references to document stream offsets
                persistentDirectories = buildPersistentDirectories(documentBytes, lastEdit);

                // Obtain a Document record
                int refToDoc = (int) LittleEndian.getUInt(documentBytes, lastEdit + RECORD_HEADER_LEN + 16);
                if (persistentDirectories[refToDoc] != -1) {
                    int offsetToDoc = (int) persistentDirectories[refToDoc];
                    int docLen = (int) LittleEndian.getUInt(documentBytes, offsetToDoc + 4);
                    int docType = LittleEndian.getUShort(documentBytes, offsetToDoc + 2);
                    if (docType != RECORD_TYPE_DOCUMENT) {
                        throw new PlainTextExtractorException("PPT parser: Document container expected");
                    } else {
                        inMasterSlideList = false;
                        firstSlide = true;
                        // Parse document
                        decode(documentBytes, offsetToDoc + RECORD_HEADER_LEN,
                               docLen, STATE_DOC_BEGIN);
                    }
                }
            }
        } catch (IOException e) {
            throw new PlainTextExtractorException(e);
        }
    }

    /**
     * Extracts persistent directories which show what records are 'up to date'
     * -- those, that contain last edits.
     *
     * @param documentBytes bytes that are extracted from the
     * 'Powerpoint Document' stream
     * @param lastEdit the offset of the last <code>UserEdit</code> record
     * @return array of long with indices from 0 to
     * <code>maxPersistWritten</code> where values are -1 if that reference
     * is not exist, and offset of the corresponding record otherwise.
     * Reference 0 is invalid so the value at index 0 is always -1.
     */
    private long[] buildPersistentDirectories(byte[] documentBytes,
                                              int lastEdit) {
        // Allocate an array of sufficient size
        int maxPersistWritten = (int) LittleEndian.getUInt(documentBytes, lastEdit + RECORD_HEADER_LEN + 20);
        long[] result = new long[maxPersistWritten + 1];
        for (int i = 0; i <= maxPersistWritten; i++) {
            result[i] = -1;
        }

        do {
            int curDirs = (int) LittleEndian.getUInt(documentBytes, lastEdit + RECORD_HEADER_LEN + 12);
            addPersistantDirectories(result, documentBytes, curDirs);
            // Get previous UserEdit record
            lastEdit = (int) LittleEndian.getUInt(documentBytes, lastEdit + RECORD_HEADER_LEN + 8);
        } while (lastEdit != 0);

        return result;
    }

    /**
     * Processes directories for a particular 'edit'. This method is called
     * from last to first 'edits' so it only adds new directories and doesn't
     * modify the existing ones.
     *
     * @param dirs existing directories (extracted from later 'edits')
     * @param documentBytes bytes that are extracted from the
     * 'Powerpoint Document' stream
     * @param curDirs the offset of the <code>PersistPtrIncrementalBlock</code>
     * that will supply directories
     */
    private void addPersistantDirectories(long[] dirs, byte[] documentBytes,
                                          int curDirs) {
        long size = LittleEndian.getUInt(documentBytes, curDirs + 4);
        int pointer = 0;
        while (pointer < size) {
            long firstField = LittleEndian.getUInt(documentBytes, curDirs + RECORD_HEADER_LEN + pointer);
            pointer += 4;
            // Number of references in the chunk
            int refNum = (int) (firstField >> 20);
            // Starting index for the chunk
            int refStart = (int) (firstField & 0xFFFFF);
            for (int i = 0; (i < refNum) && (pointer < size); i++) {
                if (dirs[refStart + i] == -1) {
                    dirs[refStart + i] = LittleEndian.getUInt(documentBytes, curDirs + RECORD_HEADER_LEN + pointer);
                }
                pointer += 4;
            }
        }
    }

    /**
     * Processes a sequence of records. For each record get its <code>type</code>
     * and, if 'automation' knows, what to do with that record, process it,
     * otherwise bypass the record.
     *
     * @param buffer byte array which contains bytes representing records
     * @param begin the beginning of first record in the <code>buffer</code>
     * @param len length of records to process
     * @param state current 'automation' state
     * @throws IOException
     */
    private void decode(byte[] buffer, int begin, int len, int state)
            throws IOException {
        // TODO: Support for PowerPoint 95 (and older?) presentations
        if ((state == STATE_SLIDE_PPDRAWING || state == STATE_NOTES_PPDRAWING) && inMasterSlideList) {
            // Ignore content of masters
            return;
        }

        int pointer = 0;
        TransitionFunctionArg arg;
        TransitionFunctionValue value;

        while (pointer < len) {
            int code = LittleEndian.getUShort(buffer, begin + pointer);
            int type = LittleEndian.getUShort(buffer, begin + pointer + 2);
            long size = LittleEndian.getUInt(buffer, begin + pointer + 4);

            // Get 'automation' instructions
            arg = new TransitionFunctionArg(state, type);
            value = (TransitionFunctionValue) map.get(arg);
            if (value != null) {
                // This record is acceptable in current state, process it
                boolean recordIsContainer = ((code & 0xF) == 0xF);
                if (recordIsContainer) {
                    if (value.state == STATE_SLIDE_LIST_WITH_TEXT && code == 31) {
                        // That is a container that contains masters
                        boolean temp = inMasterSlideList;
                        inMasterSlideList = true;
                        decode(buffer, begin + pointer + RECORD_HEADER_LEN, (int) size, value.state);
                        inMasterSlideList = temp;
                    } else {
                        decode(buffer, begin + pointer + RECORD_HEADER_LEN, (int) size, value.state);
                    }
                } else {
                    executeAction(value.action, buffer, begin + pointer + RECORD_HEADER_LEN, size);
                }
            }
            pointer += (size + RECORD_HEADER_LEN);
        }

        // Process 'container end' event
        arg = new TransitionFunctionArg(state, SYMBOL_CONTAINER_END);
        value = (TransitionFunctionValue) map.get(arg);
        if (value != null) {
            executeAction(value.action, buffer, 0, 0);
        }
    }

    /**
     * Executes an actions that correspond to particular atom in particular
     * state.
     *
     * @param action action to execute
     * @param buffer byte buffer that contains the atom record
     * @param begin the beginning of the atom in the <code>buffer</code>
     * @param len length of atom
     * @throws IOException
     */
    private void executeAction(int action, byte[] buffer, int begin, long len)
            throws IOException {
        switch (action) {
        case ACTION_HANDLE_ASCII:
            handleAscii(buffer, begin, (int) len);
            break;
        case ACTION_HANDLE_U16:
            handleU16(buffer, begin, (int) len);
            break;
        case ACTION_HANDLE_FORMATTED:
            handleFormatted(buffer, begin, (int) len);
            break;
        case ACTION_HANDLE_HEADER_FOOTER:
            handleHeaderFooter(buffer, begin, (int) len);
            break;
        case ACTION_HANDLE_SLIDE_PERSIST_ATOM:
            handleSlidePersistAtom(buffer, begin, (int) len);
            break;
        case ACTION_HANDLE_PERSIST_TEXT_ASCII:
            handlePersistTextAscii(buffer, begin, (int) len);
            break;
        case ACTION_HANDLE_PERSIST_TEXT_U16:
            handlePersistTextU16(buffer, begin, (int) len);
            break;
        case ACTION_HANDLE_SLIDE_LIST_END:
            handleSlideListEnd(buffer, begin, (int) len);
            break;
        default:
            break;
        }
    }

    private void handleSlideListEnd(byte[] buffer, int begin, int len)
            throws IOException {
        if (!firstSlide) {
            // Process current slide
            handleSlideBegin(buffer);
        }
        firstSlide = true;
    }

    private void handlePersistTextAscii(byte[] buffer, int begin, int len)
            throws IOException {
        handleAscii(buffer, begin, len);
        if (textsLeft > 0) {
            textsLeft--;
        }
    }

    private void handlePersistTextU16(byte[] buffer, int begin, int len)
            throws IOException {
        handleU16(buffer, begin, len);
        if (textsLeft > 0) {
            textsLeft--;
        }
    }

    private void handleSlidePersistAtom(byte[] buffer, int begin, int len)
            throws IOException {
        // This will begin the next slide
        if (!firstSlide) {
            // Process current slide
            handleSlideBegin(buffer);
        } else {
            firstSlide = false;
        }
        curSlideRef = (int) LittleEndian.getUInt(buffer, begin);
        textsLeft = (int) LittleEndian.getUInt(buffer, begin + 8);
    }

    private void handleSlideBegin(byte[] buffer) throws IOException {
        int curSlideOffset = (int) persistentDirectories[curSlideRef];
        int curSlideType = LittleEndian.getUShort(buffer, curSlideOffset + 2);
        int curSlideSize = (int) LittleEndian.getUInt(buffer, curSlideOffset + 4);
        switch (curSlideType) {
        case RECORD_TYPE_SLIDE:
            decode(buffer, curSlideOffset + RECORD_HEADER_LEN,
                   curSlideSize, STATE_SLIDE);
            break;
        case RECORD_TYPE_NOTES:
            decode(buffer, curSlideOffset + RECORD_HEADER_LEN,
                   curSlideSize, STATE_NOTES);
            break;
        case RECORD_TYPE_MAIN_MASTER:
            decode(buffer, curSlideOffset + RECORD_HEADER_LEN,
                   curSlideSize, STATE_MAIN_MASTER);
            break;
        default:
            break;
        }
    }

    private void handleHeaderFooter(byte[] buffer, int begin, int len)
            throws IOException {
        writer.write(new String(buffer, begin, len, "UTF-16LE"));
        writer.write(Constants.EOL);
    }

    private void handleAscii(byte[] buffer, int begin, int len)
            throws IOException {
        writer.write(new String(buffer, begin, len));
        writer.write(Constants.EOL);
    }

    private void handleU16(byte[] buffer, int begin, int len)
            throws IOException {
        writer.write(new String(buffer, begin, len, "UTF-16LE"));
        writer.write(Constants.EOL);
    }

    private void handleFormatted(byte[] buffer, int begin, int len) {
        // TODO: Extract text from "formatted" records
    }

    /**
     * Just a struct with two fields: <code>state</code> and <code>type</code>.
     * Represents an argument of the transition function.
     */
    private static class TransitionFunctionArg {
        public int state;
        public int type;

        TransitionFunctionArg(int newState, int newType) {
            state = newState;
            type = newType;
        }

        public boolean equals(Object obj) {
            TransitionFunctionArg arg = (TransitionFunctionArg) obj;
            return arg.state == this.state && arg.type == this.type;
        }

        public int hashCode() {
            int result;
            result = state;
            result = 29 * result + type;
            return result;
        }
    }

    /**
     * Just a struct with two fields: <code>state</code> and <code>action</code>.
     * Represents a value of the transition function.
     */
    private static class TransitionFunctionValue {
        public int state;
        public int action;

        TransitionFunctionValue(int newState, int newAction) {
            state = newState;
            action = newAction;
        }
    }

    /**
     * @see com.blandware.atleap.common.parsers.SpecificPlainTextExtractor#getUsedEncoding()
     */
    public String getUsedEncoding() {
        return null;
    }
}
